package hot100;

import DTO.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class levelOrder2 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //使用队列来记录每一层级的节点，添加到返回值的同时记录下一层的节点
        List<List<Integer>> ret = new ArrayList<>();
        Queue<TreeNode> que = new LinkedList<>();

        if(root == null) {
            return ret;
        }
        que.add(root);
        while(!que.isEmpty()) {
            //记录当前层级的个数
            List<Integer> tem = new ArrayList<>();
            //统计 当前层级的节点个数
            int nums = que.size();
            for(int i = 0;i < nums;i++) {
                TreeNode dem = que.poll();
                tem.add(dem.val);
                if(dem.left != null) {
                    que.add(dem.left);
                }
                if(dem.right != null) {
                    que.add(dem.right);
                }
            }
            ret.add(tem);
        }
        return ret;
    }
}
